/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM35 判断是不是完全二叉树
 * <a href="https://www.nowcoder.com/practice/8daa4dff9e36409abba2adbe413d6fae?tpId=295&tqId=2299105&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-12-28
 * Time: 22:31
 */


//完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边
//思路：因为二叉树的定义的特殊性，我们可以想到当我们在进行层序遍历的时候，空结点只会连续的出
//     现在队列尾部，且若出现空结点后又出现了非空结点，即可判断不是完全二叉树，因此根据这一
//     个特点即可编写出程序来验证是否为完全二叉树

import java.util.*;

class TreeNode {
     int val = 0;
     TreeNode left = null;
     TreeNode right = null;
     public TreeNode(int val) {
         this.val = val;
     }
 }


public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        //空树是完全二叉树
        if (root == null) {
            return true;
        }
        //辅助队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur;
        //标记遍历过程中是否已经出现空结点
        boolean flag = false;
        //层序遍历二叉树
        while (!queue.isEmpty()) {
            cur = queue.poll();
            //遇见空结点时
            if (cur == null) {
                flag = true;
                continue;
            }
            //不是空结点时，判断之前是否出现过空结点
            if (flag) {
                return false;
            }
            //左右孩子结点入队列
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }
}